package com.company.二分法;

public class Leet2398 {
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int n = chargeTimes.length;
        int ki=0,kj=n+1;
        int k = (ki+kj)/2;

        while (ki!=k){
            int sum = 0,max = 0;
            for(int i = 0;i<k;i++){
                sum += runningCosts[i];
                max = Math.max(max,chargeTimes[i]);
            }
            long minCost = max+sum*k;
            for(int i = 0;i+k<n;i++){
                sum = sum-runningCosts[i]+runningCosts[i+k];
                max = 0;
                for(int j = i+1;j<=i+k;j++){
                    max = Math.max(max,chargeTimes[j]);
                }
                minCost = Math.min(minCost,max+sum*k);
            }
            if(minCost>budget){
                kj = k;
            }else {
                ki = k;
            }
            k = (ki+kj)/2;
        }
        return k;
    }
}
